package cn.bellychang.leetcode.question025;

/**
 * @author ChangLiang
 * @date 2021/3/16
 */
public class Solution2 {

    public ListNode reverseKGroup(ListNode head, int k) {

        // 构建一个头结点，方便连接最后结果
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 指向翻转区间第一个节点的前一个节点
        ListNode tail = dummy;
        // 指向翻转区间的第一个节点
        ListNode first = tail.next;
        // 用于遍历的当前节点指针
        ListNode curr = first;
        int count = 0;
        while (curr != null) {
            count++;
            if (count == k) {
                ListNode last = curr;
                tail.next = reverseOneGroup(first, last);
                // 注意此处的first节点已经是翻转后的最后一个节点了
                tail = first;
                first = tail.next;
                curr = first;
                count = 0;
            } else {
                curr = curr.next;
            }
        }
        return dummy.next;
    }

    private ListNode reverseOneGroup(ListNode first, ListNode last) {

        // 循环不变量 是从后向前的不变量
        while (first != last) {
            ListNode curr = first;
            first = first.next;
            curr.next = last.next;
            // last节点作为翻转后的第一个节点
            last.next = curr;
        }
        return last;
    }
}
